#include "Linklist.h"

// 删除循环链表中的最小值节点，反复执行直到链表为空
void del_min(LinkList *L) {
    // 检查空链表
    if (*L == NULL || (*L)->next == *L) {
        printf("循环链表为空\n");
        if (*L != NULL) {
            free(*L);
            *L = NULL;
        }
        return;
    }

    printf("删除过程: ");

    // 反复删除最小值直到链表为空
    while ((*L)->next != *L) {  // 循环链表不为空
        LNode *pre = *L;        // 当前结点的前驱（初始为头结点）
        LNode *minPre = *L;     // 记录最小值结点的前驱
        LNode *p = (*L)->next;  // 从首元结点开始
        int min = p->data;

        // 只遍历数据结点：当 p 回到“头结点”时停止，不比较头结点
        do {
            if (p->data < min) {
                min = p->data;
                minPre = pre;
            }
            pre = p;
            p = p->next;
        } while (p != *L);   // 注意这里：不是比较到首元结点，而是到头结点

        // 输出并删除最小值结点
        printf("%d ", min);
        LNode *temp = minPre->next;     // 最小值结点
        minPre->next = temp->next;      // 踢出
        free(temp);
    }

    // 删除头结点
    free(*L);
    *L = NULL;
    printf("\n");
}

// 创建循环链表的辅助函数
LinkList CreateCircularList(ElemType arr[], int n) {
    if (n <= 0) return NULL;
    
    // 创建头结点
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL) return NULL;
    
    LNode *tail = L;  // 尾指针
    
    // 创建数据节点
    for (int i = 0; i < n; i++) {
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        if (newNode == NULL) return NULL;
        newNode->data = arr[i];
        tail->next = newNode;
        tail = newNode;
    }
    
    // 形成循环 - 尾节点指向头结点
    tail->next = L;
    
    return L;
}

// 打印循环链表
void PrintCircularList(LinkList L) {
    if (L == NULL) {
        printf("NULL\n");
        return;
    }
    
    if (L->next == L) {
        printf("Empty circular list\n");
        return;
    }
    
    printf("[");
    LNode *p = L->next;
    do {
        printf("%d", p->data);
        p = p->next;
        if (p != L) printf(", ");
    } while (p != L);
    printf("]\n");
}

// 获取循环链表长度（不包括头节点）
int getCircularLength(LinkList L) {
    if (L == NULL) return 0;
    if (L->next == L) return 0;  // 空的循环链表
    
    int count = 0;
    LNode * curr = L->next;
    do {
        count++;
        curr = curr->next;
    } while (curr != L);
    
    return count;
}

// 测试函数
int main() {
    printf("=== 删除循环链表最小值节点测试 ===\n\n");
    setvbuf(stdout, NULL, _IONBF, 0);
    // 测试1: 循环链表普通情况
    printf("测试1: 循环链表 [7, 3, 9, 1, 5]\n");
    ElemType arr1[] = {7, 3, 9, 1, 5};
    LinkList list1 = CreateCircularList(arr1, 5);
    printf("原循环链表: ");
    PrintCircularList(list1);
    del_min(&list1);
    printf("删除所有最小值后: ");
    PrintCircularList(list1);
    printf("\n");
    
    // 测试2: 循环链表最小值在开头
    printf("测试2: 循环链表最小值在开头 [1, 8, 4, 6]\n");
    ElemType arr2[] = {1, 8, 4, 6};
    LinkList list2 = CreateCircularList(arr2, 4);
    printf("原循环链表: ");
    PrintCircularList(list2);
    del_min(&list2);
    printf("删除所有最小值后: ");
    PrintCircularList(list2);
    printf("\n");
    
    // 测试3: 循环链表最小值在末尾
    printf("测试3: 循环链表最小值在末尾 [6, 4, 8, 2]\n");
    ElemType arr3[] = {6, 4, 8, 2};
    LinkList list3 = CreateCircularList(arr3, 4);
    printf("原循环链表: ");
    PrintCircularList(list3);
    del_min(&list3);
    printf("删除所有最小值后: ");
    PrintCircularList(list3);
    printf("\n");
    
    // 测试4: 循环链表单个节点
    printf("测试4: 循环链表单个节点 [100]\n");
    ElemType arr4[] = {100};
    LinkList list4 = CreateCircularList(arr4, 1);
    printf("原循环链表: ");
    PrintCircularList(list4);
    del_min(&list4);
    printf("删除所有最小值后: ");
    PrintCircularList(list4);
    printf("\n");
            
    printf("所有测试完成！\n");
    return 0;
}